package base.sort;

import base.utils.ArrayUitls;
import base.utils.PrintUtils;
import com.sun.deploy.util.ArrayUtil;
import sun.rmi.runtime.Log;

import java.util.Arrays;

/**
 * 快速排序
 * https://www.runoob.com/w3cnote/quick-sort-2.html
 */
public class QuickSort implements IArraySort {

    public int[] sort(int[] sourceArray) {
        // 对 arr 进行拷贝，不改变参数内容
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
        return quickSort(arr, 0, arr.length - 1);
    }

    /**
     * 如意理解
     */
    private int[] quickSort(int[] arr, int left, int right) {
        if (left < right) {
            int partitionIndex = partition(arr, left, right);

            quickSort(arr, left, partitionIndex - 1);       // 这里两次递归，为了把数组进行中间分割 ，当分割到最后每一组将只会有两三个，
            quickSort(arr, partitionIndex + 1, right);
        }
        return arr;
    }

    private int partition(int[] arr, int left, int right) {
        // 设定基准值（pivot）
        int pivot = left;
        int index = pivot + 1;                              // 起点设置

        PrintUtils.print(ArrayUitls.arr2String(arr));

        for (int i = index; i <= right; i++) {             // 这里交换的核心是 i ++ , 与 index ++ 的不同步，index相当于记录了 大于 pivot 的最近的 位置
            if ( arr[pivot]  >  arr[i]){                // 这里 pivot   <  i  ( i 位于pivot的右边 ) , 如果发生位置置换，index ++ , 否则说明 > arr[pivot]  , 这里 i++ , index 不变 ，
                swap(arr, i, index);
                index++;                                // 记录需要和 pivot置换的中间位置， 为和后面pivot 进行交换做准备 ，
            }
        }
        PrintUtils.print(ArrayUitls.arr2String(arr) + "; pivot = " + pivot + "-" + arr[pivot] + ";index=" + (index - 1) + "-" + arr[index - 1]);
        swap(arr, pivot, index - 1);
        return index - 1;
    }

//    {    5  ,     7    ,   6   ,  1  , 2  , 8  ,  9   }
//      pivot    index              i
//    swap(arr , index , i);    index = 1  , i = 3

//    {    5  ,     1    ,    6      ,      7  ,     2  , 8  ,  9   }
//      pivot               index                    i

//    swap(arr , index , i);    index = 2  , i = 4


//    {    5  ,     1    ,    2      ,      7  ,     6  , 8  ,  9   }
//    index = 3
//    swap(arr , pivot , index - 1 );
//    {    2  ,     1    ,    5      ,      7  ,     6  , 8  ,  9   }
//    return index - 1   ;

//---------------------------2---------------------------------------

    public void quickSort(int[] arrin) {
        int[] arr = arrin;
        quickSortRecursive(arr,0, arr.length - 1);
    }

    private void quickSortRecursive(int[] arr,int start, int end) {
        if (start >= end) return;
        int pivot = arr[end];                                   //基准值  ，支点  this选择支点为最右边
        int left = start, right = end - 1;
        while (left < right) {
            while (arr[left] <= pivot && left < right) left++;  //当存在left>pivot时停止，得到被记录的left
            while (arr[right] >= pivot && left < right) right--;//
            swap(arr,left, right);                             //当不满足 left < 基数  && right > 基数时 进行交换；正常情况left<qivot   right > qivot;
        }
        if (arr[left] >= arr[end]) swap(arr,left, end);     //当循环过后的left，是接近end的(相当于end-1的位置)
        else left++;                                        //当left不大于pivot时，选择left向右移动一位为分割线

        quickSortRecursive(arr,start, left - 1);        //相当于以end 位置对arr进行分割
        quickSortRecursive(arr,left + 1, end);
    }


    private void swap(int[] arr,int x, int y) {
        if (x != y){
            int temp = arr[x];
            arr[x] = arr[y];
            arr[y] = temp;
        }
    }


//----------------------------3--------------------------------------


    public static void quickSorter(int[] arr,int left,int right){
        int middle;
        if(left < right){
            middle = partitioner(arr,left,right);
            quickSorter(arr,left,middle-1);
            quickSorter(arr,middle+1,right);
        }
    }

    public static int partitioner(int[] arr,int left,int right){
        int pivot = arr[left];
        while(left < right){

            while(left<right && arr[right] >= pivot)
                right--;
            arr[left] = arr[right];
            while(left < right && arr[left]<= pivot)
                left++;
            arr[right] = arr[left];

        }
        arr[left] = pivot;
        return left;
    }



}
